package 不同路径;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/4/29 11:29
 * @description:
 */
public class Solution {
    public int uniquePaths(int m, int n) {
        // 重叠子问题 ==> 机器人每次都能从当前位置选择从走还是从右到达重点
        // 采用 dynamic-programming
        // ① dp数组及其下标的含义：dp[i][j]表示走到坐标（i，j）最多有多少种路径
        // ② 状态转移公式：dp[i][j] = dp[i-1][j]+ dp[i][j-1]
        // ③ dp数组初始化：第一行和第一列都需要初始化为1，因为他们只有一种路径
        // ④ 遍历顺序：先从上到下，然后从左到右。或者从左到右，从上到下（因为下一个状态的确认需要左边和上边的状态信息）
        // ⑤ 举例推到dp数组：如果 m = 3， n = 7
        //             dp:      0    1   2   3   4   5   6
        //                 0    1    1   1   1   1   1   1
        //                 1    1    2   3   4   5   6   7
        //                 2    1    3   6   10  15  21  28(answer)



        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            // row
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            // column
            dp[0][i] = 1;
        }
        // print
//        printDP(dp);
        for (int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j]+ dp[i][j-1];
                // print
//                printDP(dp);
            }
        }
        return dp[m-1][n-1];
    }


    private void printDP(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("------------------------");
    }
}
